#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<deque>
#include<stack>
#include<queue>
using namespace std;


 // Definition for a binary tree node.
  struct TreeNode {
      int val;
      TreeNode *left;
      TreeNode *right;
      TreeNode(int x) : val(x), left(NULL), right(NULL) {}
  };
 
class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        
        vector<vector<int>> result;
        if(root==NULL){
            return result;
        }
        queue<TreeNode*> Q;
        Q.push(root);
        int index = 1;
        while(!Q.empty()){
            int size = Q.size();
            vector<int> temp;
            stack<int> S;
            for(int i = 0;i<size;++i){
                
                TreeNode* tempNode = Q.front();
                Q.pop();
                if(index==1){
                    temp.push_back(tempNode->val);
                }
                if(index==0){
                    S.push(tempNode->val);
                }
                if(tempNode->left!=NULL){
                    Q.push(tempNode->left);
                }
                if(tempNode->right!=NULL){
                    Q.push(tempNode->right);
                }
            }

            if(index==1){
                index=0;
            }
            else{
                while(!S.empty()){
                    temp.push_back(S.top());
                    S.pop();
                }
                index=1;
            }
            result.push_back(temp);
        }      
        return result;

    }
};

int main(){
    Solution S;
    TreeNode* head = new TreeNode(3);
    head->left = new TreeNode(9);
    head->right = new TreeNode(20);
    head->right->left = new TreeNode(15);
    head->right->right = new TreeNode(7);
    vector<vector<int>> result =  S.levelOrder(head);
    return 0;
}